from math import sqrt, atan2, sin, cos
import sys


INF = sys.float_info.max


def distance(p, q):
    return sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)
    
    
def length(p):
    return distance(p, (0, 0))
    
    
class Point(object):
    """Simple class for points in 2D Euclidean space."""
    def __init__(self, x=0.0, y=0.0):
        self.x = float(x)
        self.y = float(y)
        
    def __repr__(self):
        return "%s(%f, %f)" % (type(self).__name__, self.x, self.y)
        
    def __getitem__(self, idx):
        if idx == 0: return self.x
        if idx == 1: return self.y
        raise KeyError("invalid index provided")
        
    def __iter__(self):
        return iter((self.x, self.y))
        
    def __add__(self, point):
        return Point(self.x + point[0], self.y + point[1])
        
    def __sub__(self, point):
        return Point(self.x - point[0], self.y - point[1])
        
    def __eq__(self, point):
        print "comparing %s to %s" % (self, point)
        return self.x == point[0] and self.y == point[1]
        
    @property
    def length(self):
        return length((self.x, self.y))
        
    @length.setter
    def length(self, l):
        try:
            r = float(l) / self.length
        except ZeroDivisionError:
            raise ValueError("cannot set length of point of length 0 (undefined angle)")
        self.x *= r
        self.y *= r
        
    @property
    def angle(self):
        return atan2(self.y, self.x)
        
    @angle.setter
    def angle(self, a):
        l = self.length
        self.x = l * cos(a)
        self.y = l * sin(a)
        
        
class Line(object):
    """Class for NON-VERTICAL straight lines, line segments, and semi-segments."""
    def __init__(self, p0, p1, open_left=True, open_right=True):
        if p0.x > p1.x:
            p0, p1 = p1, p0
        self.p0 = p0
        self.p1 = p1
        self.d = self.p1 - self.p0
        if self.d.x == 0:
            self.m = None
            self.b = None
        else:
            self.m = float(self.d.y) / (self.d.x)
            self.b = p0.y - self.m * p0.x
        self.open_left = open_left
        self.open_right = open_right
        
    @classmethod
    def segment(cls, p0, p1, open_left=False, open_right=False):
        return cls(p0, p1, open_left, open_right)
        
    def __repr__(self):
        bracket1 = "]" if self.open_left else "["
        bracket2 = "[" if self.open_right else "]"
        return "%s%s%s, %s%s" % (self.__class__.__name__, bracket1, self.p0, self.p1, bracket2)
        
    @property
    def xmin(self):
        return -INF if self.open_left else self.p0.x
        
    @property
    def xmax(self):
        return +INF if self.open_right else self.p1.x
        
    @property
    def ymin(self):
        if self.d.y == 0:
            return self.p0.y
        if self.d.y > 0:
            return -INF if self.open_left else self.p0.y
        return -INF if self.open_right else self.p1.y
        
    @property
    def ymax(self):
        if self.d.y == 0:
            return self.p0.y
        if self.d.y > 0:
            return +INF if self.open_right else self.p1.y
        return +INF if self.open_left else self.p0.y
        
    def y_at(self, x):
        return self.m * x + self.b
        
    def intersection(self, other, epsilon=0.0):
        # parallel lines
        if self.m == other.m:
            return None
            
        # other is vertical, self is not
        if other.m is None:
            self, other = other, self
            
        # self is vertical, other is not
        if self.m is None:
            x = self.p0.x
            if other.xmin - epsilon <= x <= other.xmax + epsilon:
                y = other.y_at(x)
                if self.ymin - epsilon <= y <= self.ymax + epsilon:
                    return Point(x, y)
                    
        # both segments non-vertical
        else:  
            x = float(other.b - self.b) / (self.m - other.m)
            if max(self.xmin, other.xmin) - epsilon <= x <= min(self.xmax, other.xmax) + epsilon:
                return Point(x, self.y_at(x))
        return None
        
        
if __name__ == "__main__":
    point = Point(10, 20)
    delta = Point(3, 0.7)
    line = Line(point, point + delta)
    
    P = [Point(50, 50), Point(180, 50), Point(180, 140), Point(50, 140)]
    L = []
    for i in xrange(len(P)):
        L.append(Line.segment(P[i], P[(i+1)%len(P)]))
        
    def foo():
        for segment in L:
            print "Intersecting %s with %s -> %s" % (line, segment, line.intersection(segment))
            assert line.intersection(segment) == segment.intersection(line)
    
    foo()
    